class Solution {
public:
    vector<int> stk;
    vector<std::pair<int, int>> arr;
    vector<int> height;

    int maximalRectangle(vector<vector<char>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        stk.resize(m);
        arr.resize(m);
        height.resize(m);

        int ans = 0;
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                height[j] = matrix[i][j] == '0' ? 0 : height[j] + 1;
            }
            
            ans = max(ans, largestRectangleArea());
        }
        return ans;
    }
    // int compute()
    // {
    //     int r = 0, cur, left;
    //     int n = arr.size();
    //     for(int i = 0; i < arr.size(); ++i)
    //     {
    //         while(r > 0 && arr[stk[r - 1]] >= arr[i])
    //         {
    //             cur = stk[--r];
    //             left = r > 0 ? stk[r - 1] : -1;
    //             arr[cur] = { left, i };
    //         }
    //         stk[r++] = i;
    //     }
    //     while(r > 0)
    //     {
    //         cur = stk[--r];
    //         left = r > 0 ? stk[r - 1] : -1;
    //         arr[cur] = { left, n };
    //     }

    //     int ret = 0, width, length;
    //     for(int i = 0; i < n; ++i)
    //     {
    //         width = arr[i].second - arr[i].first;
    //         length = height[i];
    //         ret = max(ret, length * width);
    //     }
    //     return ret;
    // }
    int largestRectangleArea() {
        int n = height.size();
        int r = 0, ans = 0;
        for(int i = 0, cur; i < n; ++i)
        {
            while(r > 0 && height[stk[r - 1]] >= height[i])
            {
                cur = stk[--r];
                int left = r > 0 ? stk[r - 1] : -1;
                ans = max(ans, height[cur] * (i - left - 1));
            }
            stk[r++] = i;
        }

        int cur, left;
        while(r > 0)
        {
            cur = stk[--r];
            left = r > 0 ? stk[r - 1] : -1;
            ans = max(ans, height[cur] * (n - left - 1));
        }

        return ans;
    }
};
